Page du cours et TD de logique et complexité (M1)

Le cours a lieu tous les lundi de 14h à 16h en salle 1013 (bât. Sophie Germain).
Le cours est en deux parties, la première porte sur la calculabilité et suit fidèlement le chapitre 5 de Logique mathématique (volume 2), de René Cori et Daniel Lascar. La seconde porte sur la complexité, et nous suivons les quatre premiers chapitres de Complexité Algorithmique, de Sylvain Périfel.

Le TD a lieu tous les mardis à 13h15 en salle 1013 (bât. Sophie Germain), et un jeudi sur deux à 13h45 en salle 1013 également.

Un début de poly est disponible. Il contient des erreurs, merci de me les signaler !

Examen le mercredi 19 décembre de 9h30 à 12h30, en salle 278F (Halle aux farines).

Devoirs

• DM1 et son corrigé.
• DM2 et son corrigé.
• DM3.

Exercices

• TD1: Fonctions récursives primitives et son corrigé.
• TD2: Fonctions récursives et son corrigé.
• TD3: Théorème s-n-m, théorèmes de Rice et de point fixe et son corrigé.
• TD4: Machines de Turing, hiérarchie en temps, temps polynomial et son corrigé.
• TD5: Non déterminisme et classe NP et son corrigé.

Progression

• Lundi 10 septembre: fonctions récursives primitives: définitions, exemples de base, schéma µ borné (poly jusqu'à section 1.3 incluse). TD mardi seulement.
• Lundi 17 septembre: compléments sur les ensembles récursifs primitifs, fonction d'Ackerman.
• Lundi 24 septembre: fonctions récursives, machines de Turing, les fonctions récursives sont calculables par une machine de Turing (manque la stabilité par récurrence et schéma µ).
• Lundi 1er octobre: fin de la calculabilité des fonctions récursives, les fonctions calculables sont récursives.
• Lundi 8 octobre: Machine de Turing universelle, applications.
• Lundi 15 octobre: Théorème s-n-m, théorème de Rice, théorèmes de point fixe.
• Lundi 22 octobre: Définition des machines de Turing pour la complexité, classes DTIME.
• Lundi 29 octobre: Vacances.
• Lundi 5 novembre: Théorème d'accélération linéaire, théorème de réduction de l'alphabet.
• Lundi 12 novembre: Machine universelle avec perte de temps quadratique, théorème de hiérarchie en temps déterministe.
• Lundi 19 novembre: Machines non déterministes, machine universelle non déterministe, théorème de hiérarchie en temps non déterministe.
• Lundi 26 novembre: Le problème P=NP ? NP-complétude de SAT.
• Lundi 3 décembre: NP-complétude de 3-SAT et de IND-SET. Introduction à la complexité en espace: définition de L, NL, PSPACE et NPSPACE; réduction en espace logarithmique, ACCESS est NL-complet, théorème de Savich: PSPACE=NPSPACE.